import numpy as np
import matplotlib.pyplot as mp
import math as ma


def distance(a,b,B):
    return ma.sqrt(((B[b][0]-B[a][0])*(B[b][0]-B[a][0]))+((B[b][1]-B[a][1])*(B[b][1]-B[a][1])))


def fill_distance_matrix(T):
    n = len(T)
    M = np.zeros((n,n))
    for i in np.arange(0,n):
        for j in np.arange(i,n):
            M[i][j] = distance(i, j, T)
            M[j][i] = M[i,j]
    return M


#def distance_euclidienne(x,y,u,v):
#    return sqrt( (x-u)**2 + (y-v)**2) 


#renvoie le tableau des couts du cycle reference par L[i]
def recherche_cout(L, M): #L liste des cycles, M matrice des couts
    #n = M.shape[0] #nb de sommets
    C = np.zeros(len(L))
    i = 0
    for s in L: #s est un des cycles de L
        for j in np.arange(0, len(s)): #iteration sur les elements de s
            a = s[j]
            b = s[(j+1)%len(s)] #b est l'element apres a dans le cycle, donc le premier si a est le dernier
            C[i] += M[a][b] #somme partielle des couts de M
        i+=1
    return C


def cycle_minimum(s, L, C):
    cout_minimum = C[0]
    cycle_min = L[0]
    i = 0
    for c in L:
        if s in c:
	    if C[i] < cout_minimum:
		cycle_min = c
		cout_minimum = C[i]
	i += 1
    return (cycle_min, cout_minimum)

#print les sommets

#B = lecture("nodes.txt") #coordonnees des points
#M = fill_distance_matrix(B) #matrice symetrique des couts entre deux villes i et j
#L = enumerer_cycles(len(B)) #liste des cycles
#S = relaxation(L,M) #liste des arretes solution par algo set cover

#print sommets et arretes solution

#print M

#L=[ [1,6,17,2,13], [7,12,9,13,25], [16,3,24,10,18], [5, 29, 15, 3], [4,14,27,22], [20,2,19,21,8,14]]
#C=[8, 6, 27, 8, 9, 5]
#print recherche_cout(L,M)

#print cycle_minimum(14, L, C)
